Given a string s, return the number of substrings that have only one distinct letter.
Example 1:
Input: s = "aaaba" Output: 8 Explanation: The substrings with one distinct letter are "aaa", "aa", "a", "b". "aaa" occurs 1 time. "aa" occurs 2 times. "a" occurs 4 times. "b" occurs 1 time. So the answer is 1 + 2 + 4 + 1 = 8.
Example 2:
Input: s = "aaaaaaaaaa" Output: 55
Constraints:
1 <= s.length <= 1000s[i]consists of only lowercase English letters.
Average Rating: 5.00 (6 votes)
Solution
Approach 1: Arithmetic Sequence
Intuition
Note that given a string s, there are:
-
substrings with size
1:len(s); -
substrings with size
2:len(s) - 1;...
-
substrings with size
len(s) - 1:2; -
substrings with size
len(s):1.
Therefore, the number of substrings of s is 1 + 2 + ... + (len(s) - 1) + len(s), which is an Arithmetic Sequence. If you are familiar with the Sum Equation of Arithmetic Sequence, it's obvious that the number of substrings is (1 + len(s)) * len(s) / 2. If not, I'll also provide a rough analysis here for your reference.
Given a list of numbers
1, 2, 3, ..., n-1, n, an interesting fact is that:
- 1 + n = n + 1
- 2 + (n - 1) = n + 1
- 3 + (n - 2) = n + 1
- ...
If
nis an even number, there would ben / 2pairs of numbers summed ton + 1. Hence the sum of all numbers is simply(1 + n) * n / 2. Moreover, this applies to cases whennis an odd number!
Notice that, if a string contains only one distinct letter, all of its substrings are formed by one distinct letter as well.
For example, all substrings of aaa contain only one distinct letter a: a, aa, and aaa.
Therefore, to find the number of substrings that contain only one distinct letter, we can first find the longest continuous segments with only one distinct letter; then we can apply the formula mentioned above to calculate the number of substrings of each segment.
Figure 1. Find the longest continuous segments with one distinct letter and count the substrings.
Algorithm
- Initialize an integer variable
totalto count the number of substrings along with the iteration; initialize two pointersleftandrightwhich mark the beginning and the end of the substring that contains only one distinct letter. - Iterate through
S:- If we do not reach the end and the new character
S[right]is the same as the beginning oneS[left], incrementrightby 1 to keep exploringS; - otherwise, calculate the length of the substring as
right - leftand apply the Sum Equation of Arithmetic Sequence; remember to setrightasleftto start exploring the new substring.
- If we do not reach the end and the new character
Complexity Analysis
- Time Complexity: O(N), where N is the length of
S. This is because we iterate throughSonce. - Space Complexity: O(1).
This is because we do not use additional data structures.
Approach 2: Dynamic Programming
Intuition
Given a string S, we may define an integer array substrings[] with a length of len(S), such that substrings[i] is the number of substrings ending with S[i] which contains only one distinct letter S[i]. Therefore, if S[i] == S[i - 1], substrings[i] would be substrings[i - 1] + 1 where 1 refers to the substring containing only S[i]; else if S[i] != S[i - 1], substrings[i] would be 1.
For those who like mathematical definitions, you may find the state transition function as follows. Otherwise, feel free to skip this part.
Algorithm
- Initialize an integer
totalto count the number of substrings during the iteration, and an integer arraysubstringsto record the number of substrings ending withS[i]containing only one distinct letterS[i]. - Initialize
substrings[0]to 1. - Iterate
Sskipping the first element as we've initializedsubstrings[0]:- if
S[i-1] == S[i], setsubstrings[i]tosubstrings[i-1] + 1; - else, set
substring[i]to 1. - increment
totalbysubstrings[i].
- if
Note that substrings[i] only depends on substrings[i - 1], therefore instead of using an array, we can use an integer variable count to keep track of substrings[i] to improve the space complexity from O(N) to O(1).
Complexity Analysis
- Time Complexity: O(N), where N is the length of
S. This is because we iterate throughSonce. - Space Complexity: O(1).
The original implementation of this dynamic programming approach takes O(N) space complexity as it uses an array with a size of
len(S). With the optimization, we achieve O(1) space complexity because we do not use additional data structures.
Simple 2 pointer solution: https://leetcode.com/problems/count-substrings-with-only-one-distinct-letter/discuss/1003859/Java-2-Pointer-Solution-Beats-100
You don't have any submissions yet.
xxxxxxxxxxclass Solution {public: int countLetters(string s) { }};